# _*_coding:utf-8_*_

# 题目：假设商店老板需要找零 n 元钱，钱币的面额有100元，50元，20元，5元，1元，如何找零使得所需钱币的数量最少？（注意：没有10元的面额）
# 需求：如果需要找  376元零钱，如何使得所需钱币最少？

# 思路：我们需要从大额钱币开始，然后往小额钱币遍历，这样才能保证数量最少。

# t表示商店有的零钱的面额
t = [100, 50, 20, 5, 1]


# n 表示n元钱
def change(t, n):
    m = [0 for _ in range(len(t))]
    for i, money in enumerate(t):
        m[i] = n // money  # 除法向下取整
        n = n % money  # 除法取余
    return m, n


print(change(t, 376))  # ([3, 1, 1, 1, 1], 0)

# 我对自己写的代码的时间复杂度和空间复杂度的理解是：空间复杂度为O(n)，时间复杂度为O(n)
